The present invention relates to the efficiency of data accessing techniques, and more specifically, to Distributed Lock Manager (DLM) lock conversions.
In order to promote efficiency, computer networks have been developed in which processes running on many computer devices or xe2x80x9cnodesxe2x80x9d can share resources. For example, instead of having to purchase one printer for every computer, users may purchase a single printer that may be connected to a network that has many computers. Processes on each computer on the network access the printer only when the processes require the printer.
Moreover, in some circumstances, certain types of resources, such as data blocks of a storage medium or tables stored on a storage medium must necessarily be shared so that all the users on the network get the same information. For example, consider a hypothetical company, Acme, which needs to track its inventory. A database containing Acme""s inventory information and which is constantly updated by various users in the company is useful only if all users of the database have access to the same information at any given time. On the other hand, if Acme maintained several independent databases on the same set of inventory, with some users updating some of the information on one database and some other users updating information on a different database, then none of these databases, by themselves, would correctly reflect the inventory in Acme. Thus, maintaining a multiplicity of independent inventory databases in Acme would be meaningless because the goal is to enable the users to share with each other the most up-to-date and accurate information on Acme""s inventory in the most efficient manner.
However, the sharing of resources cannot be done in a haphazard fashion but rather in a managed and orderly fashion. For example, a resource such as a table stored on a storage medium, may be concurrently accessed in some ways (e.g. read) by multiple processes, but accessed in other ways (e.g. written to) by only one process at a time. Consequently, mechanisms have been developed which control access to resources.
One such mechanism is referred to as a lock. A lock is a data structure that indicates that a particular process has been granted certain rights with respect to the resource. There are many types of locks. Some types of locks may be shared by many processes, while other types of locks prevent any other locks to be granted on the same resource.
Due to the various permissions and guarantees associated with these locks, certain lock combinations are not allowed. For example ownership of an exclusive lock grants a process permission to do anything with a resource, and guarantees that no other process is performing any operation on the resource. Thus if a process owns an exclusive mode lock on a resource, then no other process can be granted any lock other than a NULL mode lock, which grants a process no permission to access the resource in any manner. Thus, the ownership of locks has to be managed in a manner to provide for efficient accessing of resources.
One management approach is to use a lock manager, an entity that is responsible for granting, queuing, and keeping track of locks on one or more resources. Before a process can perform an operation on a resource, the process is required to obtain a lock that grants to the process the right to perform the desired operation on the resource. To obtain a lock, a process transmits a request for the lock to a lock manager. To manage the use of resources in a network system, lock managers are executed on one or more nodes in the network. Associated with the use of lock managers is an overhead in the form of messages being passed back and forth between the nodes of the computer network. For example, in order to obtain a lock, a process residing on one node may have to send a message to a lock manager residing on a different node.
According to one implementation, a lock manager implements two types of objects: a resource object and a lock. Resource objects are data structures that correspond to actual resources. An application that uses a lock manager establishes a mapping between actual resources and resource objects. Each resource object has two queues: a granted queue and a convert queue. The granted queue is an unordered list of locks that have been granted. The convert queue is a partially ordered list of locks that have been requested, but not yet granted. Typically, a request for a lock is actually a convert request, where a process holding a lock is requesting that the lock it holds be converted from one mode of lock to a different mode of lock.
Locks are data structures that identify a process and a lock mode. Lock managers attach locks to the granted queues of resource objects to indicate that the process identified in the lock has been granted a lock of the type indicated in the lock on the resource that corresponds to the resource object to which the lock is attached.
FIG. 1 is a block diagram illustrating a typical lock manager 106. Lock manager 106 is a process that is configured to manage a resource object 100 stored in a memory 108. The resource object includes a granted queue 102 and a convert queue 104. Lock manager 106 has attached three locks 110, 112 and 114 to the granted queue 102, and one convert request 130 to the convert queue 104.
All locks and convert requests have a process ID portion and a lock mode portion. The process ID portion 16 of lock 110 indicates that a process PROC_1 owns lock 110, and the lock mode portion 118 of lock 110 indicates that lock 110 is an exclusive lock. The process ID portion 120 of lock 112 indicates that lock 112 is owned by a process PROC_2, and the lock mode portion 122 of lock 112 indicates that lock 112 is a NULL mode lock. The process ID portion 124 of lock 114 indicates that lock 114 is owned by a process PROC_3, and the lock mode portion 126 of lock 114 indicates that lock 114 is a NULL lock. The process ID portion 132 of convert request 130 indicates that convert request 130 is associated with process PROC_4, and the lock mode portion 136 of convert request 130 indicates that PROC_4 currently holds a NULL mode lock on the resource. In addition to a lock mode portion 136, convert request 130 has a requested mode portion 134 that indicates that PROC_4 is requesting an exclusive mode lock.
Lock manager 106 has attached locks 110, 112 and 114 to granted queue 102, indicating that PROC_1 currently has exclusive ownership of the resource that corresponds to resource object 100. Lock manager 106 has attached convert request 130 to the convert queue 104, indicating that PROC_4 has requested but has not yet been granted an exclusive mode lock on the resource associated with resource object 100.
Information pertaining to any given resource may be stored in the resource object that corresponds to the resource. Each resource object is stored in the memory of a single node. The node on which a resource object is stored is referred to as the master node for the resource object.
According to one lock management approach, a process initially establishes a NULL mode lock on all resources that the process will possibly use. Then, when the process actually requires access to a resource, the process requests that its NULL mode lock be converted to a lock that grants to the process the rights to perform the desired operation.
For example, to delete a resource such as a table stored on a storage medium, a process must obtain an exclusive mode lock on the resource object that corresponds to the table. To obtain the exclusive mode lock, the process transmits a message to the lock manager that controls the resource object that corresponds to the table. In the message, the process requests that its current NULL mode lock be converted to an exclusive mode lock. If no other process has requested a conversion, and if no currently granted locks would prevent the grant of an exclusive mode lock, then the current lock held by the requesting process is converted to an exclusive mode lock. Once the lock manager performs the requested conversion, the lock manager transmits a message to the requesting process to indicate that the requested conversion operation has been performed.
If a process requires access to read data from a table, the process must obtain a shared mode lock. To obtain a shared mode lock, the process requests the lock manager that controls the resource object that corresponds to the table to convert its current lock to a shared mode lock. If no other process has requested a conversion, and if no currently granted locks would prevent the grant of a shared mode lock, then the current lock held by the requesting process is converted to a shared mode lock.
If an exclusive mode lock has already been granted for the table, then a shared mode lock cannot be granted. Under these circumstances, the lock convert request is placed on the convert queue of the resource object. When the blocking process is ready to release its exclusive lock, the blocking process may send a lock downgrade request to the lock manager. The lock manager responds by converting the exclusive mode lock to a lesser lock that allows the grant of the shared mode lock. The shared mode lock is then granted by moving the shared mode lock request from the convert queue to the granted queue and transmitting a message to the requesting process to inform the requesting process that the shared mode lock has been granted.
The convert queue of a resource object is a partially ordered list that holds all outstanding (ungranted) lock requests. If any outstanding lock requests have not been granted, one of the ungranted lock requests will be at the xe2x80x9cheadxe2x80x9d of the convert queue. Even if the currently granted locks do not prevent a lock manager from granting a particular lock request, the lock request is placed on the convert queue if the convert queue is not empty. This policy prevents xe2x80x9clivelocksxe2x80x9d, where one process cannot make progress in the system while other processes can.
In networked computer systems, some or all of the processes that are holding and requesting locks on a particular resource may be on different nodes than the node that contains the resource object that corresponds to the resource. For example, the process desiring a lock and the lock resource may reside within different nodes of a multi-processor machine, or on different workstations in a local area network. Consequently, all of the messages that pass between the lock-requesting processes and the lock manager must be transmitted between nodes over the network. The computational power that must be expended to facilitate such inter-node messages is significant relative to the power required for intra-node communication. In addition, inter-node communication is generally slower than intra-node communication. Further, the inter-node traffic thus generated reduces the throughput available for other types of inter-node traffic, which may be significant when the inter-node traffic is between workstations on a network.
FIG. 2 illustrates a computer system in which four nodes 202, 206, 210 and 214 are connected through a network 216. Nodes 202, 206 and 210 are executing process 204 (PROC_1), process 208 (PROC_2) and process 212 (PROC_3), respectively. Lock manager 106 is resides on node 214. Every time one of processes 204, 208 and 212 wish to acquire, upgrade, downgrade or release a lock on a resource object controlled by lock manager 106, the processes must send messages to node 214 through network 216. Every time a convert request is granted on lock manager 106, a message must be sent from node 214 to the node on which resides the process that requested the lock conversion.
In yet another approach, managing access to resources is performed by a Distributed Lock Manager (DLM). The DLM provides for a distributed resource object architecture to spread the lock management processing for any given resource among multiple nodes as opposed to a centralized resource object, and to reduce the amount of inter-node traffic required to perform lock management operations. Due to the high computational costs associated with inter-node communication, a further reduction in inter-node traffic is desirable.
Based on the foregoing, it is clearly desirable to provide a mechanism for allocating locks between processes that requires less inter-node traffic.
A method and apparatus for managing access to a resource using anticipatory lock conversions in a distributed lock management system is provided. According to one aspect of the invention, a lock conversion request with respect to any resource may contain an anticipatory lock conversion request. A distributed lock manager, if it can, will grant the more restrictive lock mode indicated by the anticipatory lock conversion request.